Disclaimer: Dieser Teil des Workshops basiert zum Teil auf dem Datacamp-Kurs “Network Analysis in R”

Zur Veranschaulichung nutzen wir das Forest Gump Network: Each edge of the network indicates that those two characters were in at least one scene of the movie together. Therefore this network is undirected.

gump_raw <- read_csv("../data/gump.csv")
## Parsed with column specification:
## cols(
##   V1 = col_character(),
##   V2 = col_character()
## )
head(gump_raw, 15)
## # A tibble: 15 x 2
##    V1              V2               
##    <chr>           <chr>            
##  1 ABBIE HOFFMAN   JENNY            
##  2 ABBIE HOFFMAN   POLICEMAN        
##  3 ANCHORMAN       FORREST          
##  4 ANCHORMAN       LT DAN           
##  5 ANCHORMAN       MARGO            
##  6 ANCHORMAN       MRS GUMP         
##  7 ANCHORMAN       PRESIDENT JOHNSON
##  8 ANNOUNCER       FORREST          
##  9 ANNOUNCER       JENNY            
## 10 ANNOUNCER       LT DAN           
## 11 ANOTHER DAY     BUBBA            
## 12 ANOTHER DAY     NIGHT            
## 13 ANOTHER DAY     SONG             
## 14 ASSISTANT COACH FOOTBALL COACH   
## 15 ASSISTANT COACH FORREST
gump_net <- gump_raw %>% as.matrix() %>% igraph::graph_from_edgelist(directed = FALSE)
gump_net
## IGRAPH babf477 UN-- 94 271 -- 
## + attr: name (v/c)
## + edges from babf477 (vertex names):
##  [1] ABBIE HOFFMAN  --JENNY             ABBIE HOFFMAN  --POLICEMAN        
##  [3] ANCHORMAN      --FORREST           ANCHORMAN      --LT DAN           
##  [5] ANCHORMAN      --MARGO             ANCHORMAN      --MRS GUMP         
##  [7] ANCHORMAN      --PRESIDENT JOHNSON FORREST        --ANNOUNCER        
##  [9] JENNY          --ANNOUNCER         LT DAN         --ANNOUNCER        
## [11] ANOTHER DAY    --BUBBA             ANOTHER DAY    --NIGHT            
## [13] ANOTHER DAY    --SONG              ASSISTANT COACH--FOOTBALL COACH   
## [15] FORREST        --ASSISTANT COACH   BERT           --ERNIE            
## + ... omitted several edges
plot.igraph(gump_net, layout = layout_nicely, vertex.label.cex=0.7, vertex.size = 0)

Netzwerkdaten

Netzwerkdaten können in unterschiedlichen Formaten vorliegen. Wir haben gerade die – besonders für große Netzwerke – geläufige Form der edge list gesehen, die sehr platzsparend Netzwerkdaten speichern kann.

get.edgelist(gump_net) %>% head(15)
##       [,1]              [,2]               
##  [1,] "ABBIE HOFFMAN"   "JENNY"            
##  [2,] "ABBIE HOFFMAN"   "POLICEMAN"        
##  [3,] "ANCHORMAN"       "FORREST"          
##  [4,] "ANCHORMAN"       "LT DAN"           
##  [5,] "ANCHORMAN"       "MARGO"            
##  [6,] "ANCHORMAN"       "MRS GUMP"         
##  [7,] "ANCHORMAN"       "PRESIDENT JOHNSON"
##  [8,] "FORREST"         "ANNOUNCER"        
##  [9,] "JENNY"           "ANNOUNCER"        
## [10,] "LT DAN"          "ANNOUNCER"        
## [11,] "ANOTHER DAY"     "BUBBA"            
## [12,] "ANOTHER DAY"     "NIGHT"            
## [13,] "ANOTHER DAY"     "SONG"             
## [14,] "ASSISTANT COACH" "FOOTBALL COACH"   
## [15,] "FORREST"         "ASSISTANT COACH"

Häufig kommen Netzwerkdaten aber auch in Matrixform vor. Diese sogenannte adjacency-matrix ist quadratisch, beinhaltet also genauso viele Zeilen wie Spalten. Jede Zelle gibt an ob eine Verbindung zwischen Zeile X und Spalte Y besteht.

gump_net %>% igraph::get.adjacency(sparse = FALSE) %>% data.frame() %>% .[1:5,1:5]
##               ABBIE.HOFFMAN JENNY POLICEMAN ANCHORMAN FORREST
## ABBIE HOFFMAN             0     1         1         0       1
## JENNY                     1     0         1         0       1
## POLICEMAN                 1     1         0         0       1
## ANCHORMAN                 0     0         0         0       1
## FORREST                   1     1         1         1       0

Meistens existieren noch weitere Attribute, die man den Knoten hinzufügen möchte. Dies können bspw. verschiedene Arten von Knoten im Netzwerk sein (Geschlecht, Parteizugehörigkeit, ethnische Zugehörigkeit, …) oder aber auch direkte Anweisungen für die Grafik. Das sind dann z.B. Attribute wie Farbe des Knotens oder ob der Knoten als Kreis oder Quadrat dargestellt werden soll. Auch der Knotenname ist meist ein eigenes Attribut. Oftmals basiert eine vernünftige Netzwerkvisualisierung auf der Nutzung dieser Attribute. Dabei können sowohl die Knoten als auch die Verbindungen zwischen ihnen (edges) eigene Attribute besitzen.

list.vertex.attributes(gump_net)
## [1] "name"
V(gump_net)$degree <- degree(gump_net, mode = "all")
list.vertex.attributes(gump_net)
## [1] "name"   "degree"
plot.igraph(gump_net, vertex.size = V(gump_net)$degree/2, layout = layout_nicely, vertex.label.cex=0.5)

Netzwerke können aufgrund von diesen Attributen auch weiter unterteilt oder eingeschränkt werden. Hier werden nur die Knoten ausgewählt, die ein degree von über 5 aufweisen und dem neuen Objekt gump_net1 zugewiesen.

table(V(gump_net)$degree)
## 
##  1  2  3  4  5  6  7  8  9 10 11 19 45 89 
## 10 24  5 10 16 10  1 11  1  1  2  1  1  1
gump_net1 <- induced.subgraph(gump_net, vids=V(gump_net)$degree > 5)
plot.igraph(gump_net1, vertex.size = V(gump_net1)$degree/2)

Analyse einzelner Knoten

Bei Netzwerken kann man zwischen der Analyse einzelner Individuen im Netzwerk und der Beschreibung der gesamten Netzwerkstruktur unterscheiden. Der Übersichtlichkeit wegen, werden im Folgenden häufig nur die Werte der ersten 6 Knoten im Netzwerk ausgegeben.

V(gump_net)$name[1:6]
## [1] "ABBIE HOFFMAN" "JENNY"         "POLICEMAN"     "ANCHORMAN"    
## [5] "FORREST"       "LT DAN"
vcol <- rep("grey80", vcount(gump_net))
vcol[1:6] <- "gold"
vlabel <- V(gump_net)$name
vlabel[7:length(vlabel)] <- ""

plot(gump_net, vertex.label=vlabel, vertex.color=vcol, vertex.label.cex = 0.8, layout = layout_nicely, vertex.size = 10)

degree

Der Grad eines Netzwerks ist ein einfaches Zentralitätsmaß, das zählt, wie viele Nachbarn ein Knoten hat. Wenn das Netzwerk gerichtet ist, haben wir zwei Versionen des Maßes: Der in-degree ist die Anzahl der eingehenden Verbindungen während der out-degree die Anzahl der ausgehenden Kanten ist. In einem ungerichteten Netzwerk ist der in- und der out-degree identisch.

degree(gump_net) %>% head()
## ABBIE HOFFMAN         JENNY     POLICEMAN     ANCHORMAN       FORREST 
##             6            45             6             5            89 
##        LT DAN 
##            19
which.max(degree(gump_net))
## FORREST 
##       5

betweenness

Die Betweenness misst das Ausmaß, in dem ein Knoten auf Pfaden zwischen anderen Knoten liegt. Knoten mit hoher Betweenness können einen erheblichen Einfluss innerhalb eines Netzwerks haben, da sie die gegenseitige Übermittlung von Informationen beeinflussen. Sie sind auch diejenigen, deren Entfernung aus dem Netzwerk die Kommunikation zwischen anderen Knoten am meisten stört.

betweenness(gump_net) %>% head()
## ABBIE HOFFMAN         JENNY     POLICEMAN     ANCHORMAN       FORREST 
##       0.00000     582.61667       0.00000      32.23333    3453.80000 
##        LT DAN 
##     120.01667

eigenvector centrality

Die Eigenvektorzentralität ist quasi die Erweiterung der degree-Zentralität. Bei der degree-Zentralität wird für jede Verbindung ein Punkt vergeben. Es sind jedoch nicht alle Knoten gleichwertig: Einige sind relevanter als andere und vernünftigerweise zählen Verbindungen zu wichtigen Knoten mehr. Daher ist die These der Eigenvektorzentralität:

Ein Knoten ist wichtig, wenn er mit anderen wichtigen Knoten verbunden ist.

Die Eigenvektor-Zentralität unterscheidet sich von der Grad-Zentralität: Ein Knoten, der viele Verbindungen hat, muss nicht notwendigerweise eine hohe Eigenvektor-Zentralität haben (es könnte sein, dass alle Kontakte nur zu sehr wenigen anderen Knoten Kontakte haben). Darüber hinaus ist ein Knoten mit hoher Eigenvektor-Zentralität nicht notwendigerweise stark verknüpft (der Knoten kann wenige, aber wichtige Kontakte haben).

eigen_centrality(gump_net)$`vector`[1:6]
## ABBIE HOFFMAN         JENNY     POLICEMAN     ANCHORMAN       FORREST 
##     0.1799188     0.6482939     0.1799188     0.1209687     1.0000000 
##        LT DAN 
##     0.3388870

closeness centrality

Die closeness centrality misst die mittlere Entfernung von einem Scheitelpunkt zu anderen Scheitelpunkten. Dabei werden wieder die Pfade genutzt, also die geodätische, kürzeste Distanz zwischen zwei Knoten.

Dieser Wert nimmt niedrige Werte für Scheitelpunkte an, die durchschnittlich nur durch eine kurze geodätische Entfernung von anderen getrennt sind. Solche Scheitelpunkte haben möglicherweise einen besseren Zugriff auf Informationen an anderen Knoten oder einen direkteren Einfluss auf andere Akteure.

closeness(gump_net) %>% head()
## ABBIE HOFFMAN         JENNY     POLICEMAN     ANCHORMAN       FORREST 
##   0.005494505   0.007092199   0.005494505   0.005434783   0.010309278 
##        LT DAN 
##   0.005952381

weitere Zentralitätswerte

Hier wurden nur die geläufigsten Zentralitätswerte aufgeführt. Es gibt noch zahlreiche weitere mögliche Werte. Weitere häufiger vorkommende Zentralitäten findet man unter folgenden Stichpunkten:

  • PageRank centrality
  • Bonacich power
  • Flow betweenness
  • Load centrality
  • Information centrality
  • Stress centrality
  • Harary graph
  • Bonacich alpha
  • Kleinberg authority
  • Kleinberg hub

Subgroups and communities

Granovetter (1973) schlug in seinem Klassiker “Die Stärke der schwachen Bindungen (1973)” vor, dass viele soziale Netzwerke aus vielen relativ dicht verbundenen Untergruppen (z. B. Freundschafts-Subnetzwerken) bestehen, die selbst nur über weniger starke Bindungen (z.B. miteinander verbunden Bekannte) miteinander verbunden sind. Daraus folgt, dass es wichtig ist, solche Untergruppen definieren und identifizieren zu können.

Ein grundlegendes Merkmal sozialer Netzwerke (verglichen mit zufälligen Netzwerken) ist daher das Vorhandensein von Clustering oder die Neigung, Gruppen zu bilden. Der Prozess findet in einem sozialen Netzwerk statt, wenn bspw. zwei Personen, die einen gemeinsamen Freund haben, auch selbst Freunde werden. Viele Algorithmen in der sozialen Netzwerkanalyse basieren auf dieser Idee der Analyse von geschlossenen Dreiecken (Triaden).

Transitivity

Das Ausmaß, wie stark ein Netzwerk untereinander verbunden ist, kann in einem sozialen Netzwerk durch die Transitivität gemessen werden. Transitivität ist definiert als das Verhältnis geschlossener Dreiecke (Triaden, bei denen alle drei Bindungen beobachtet werden) zur Gesamtzahl aller möglichen Dreiecke (Triaden, bei denen entweder zwei oder alle drei Bindungen beobachtet werden). Die Transitivität ist also wie die Dichte ein Verhältnis, das zwischen 0 und 1 liegen kann.

transitivity(gump_net)
## [1] 0.1918082

Cliquen

Cliquen sind eine der einfachsten Arten zusammenhängender Untergruppen und aufgrund ihrer einfachen Definition auch eine der am leichtesten zu verstehenden Arten. Eine Clique ist ein maximal vollständiger Teilgraph. Das heißt, es ist eine Teilmenge von Knoten, die alle möglichen Bindungen untereinander haben. Zwischen allen beteiligten Knoten in einer Clique besteht eine direkte Verbindung. Alternativ wird das Konzept der k-cores genutzt. Dabei wird die strenge Regel, dass JEDER in der Clique mit ALLEN anderen verbunden sein muss, etwas gelockert.

# cliques(gump_net) # list of cliques       

sapply(cliques(gump_net), length)
##    [1] 1 1 1 1 1 1 2 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
##   [35] 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3 2 3 2 3 2 2 1 2 3 2
##   [69] 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 3 2 1 2 3 2 1 2 3 2
##  [103] 1 2 3 2 2 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1
##  [137] 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 4 3 2 3
##  [171] 4 3 2 3 2 1 2 3 4 3 2 3 2 1 2 3 4 3 2 3 2 1 2 3 4 3 2 3 2 1 2 3 4 3
##  [205] 2 3 2 1 2 3 4 3 2 3 2 1 2 3 4 3 2 3 2 1 2 3 4 3 2 3 2 1 2 3 4 3 2 3
##  [239] 2 1 2 3 4 3 2 3 2 1 2 3 4 3 2 3 2 3 2 2 1 2 3 4 3 2 3 3 2 2 1 2 3 4
##  [273] 3 2 3 2 1 2 3 4 3 2 3 2 1 2 3 3 2 3 2 3 2 2 1 2 3 4 5 4 3 4 3 2 3 4
##  [307] 3 2 3 2 1 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 4 3 4 3 2 3 4 3 2
##  [341] 3 2 1 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 4 3 4 3 2 3 4 3 2 3 4
##  [375] 3 2 3 2 3 2 1 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 4 3 4 3 2 3 4
##  [409] 3 2 3 2 1 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 4 3 4 3 2 3 4 3 2
##  [443] 3 2 1 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4
##  [477] 3 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2
##  [511] 3 4 3 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 3 2 1 2 3 4 5 6 5 4 5 4 3 4 5 4
##  [545] 3 4 3 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4
##  [579] 3 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2
##  [613] 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4
##  [647] 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 4
##  [681] 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 4 3 4
##  [715] 3 2 3 4 3 2 3 2 1 2 3 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 5 4 5 4
##  [749] 3 4 5 4 3 4 3 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 4 3 4 3 2 3 4
##  [783] 3 2 3 2 1 2 3 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 5 4 5 4 3 4 5 4
##  [817] 3 4 3 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2
##  [851] 1 2 3 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2
##  [885] 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4
##  [919] 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 6
##  [953] 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 6 7 8
##  [987] 7 6 7 6 5 6 7 6 5 6 5 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 7 6 5 6
## [1021] 5 4 5 6 5 4 5 4 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 6 7 6 5 6 5 4
## [1055] 5 6 5 4 5 4 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 6 5 4 5 4 3 4 5 4
## [1089] 3 4 3 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4 5 6 7 8 7 6 7 6 5 6 7 6
## [1123] 5 6 5 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4
## [1157] 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4
## [1191] 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 4
## [1225] 3 4 3 2 3 4 3 2 3 2 3 2 1 2 3 4 5 6 7 8 9 8 7 8 7 6 7 8 7 6 7 6 5 6
## [1259] 7 8 7 6 7 6 5 6 7 6 5 6 5 4 5 6 7 8 7 6 7 6 5 6 7 6 5 6 5 4 5 6 7 6
## [1293] 5 6 5 4 5 6 5 4 5 4 3 4 5 6 7 8 7 6 7 6 5 6 7 6 5 6 5 4 5 6 7 6 5 6
## [1327] 5 4 5 6 5 4 5 4 3 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 5 4 5 4 3 4
## [1361] 5 4 3 4 3 2 3 4 5 6 7 8 7 6 7 6 5 6 7 6 5 6 5 4 5 6 7 6 5 6 5 4 5 6
## [1395] 5 4 5 4 3 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 5 4 5 4 3 4 5 4 3 4
## [1429] 3 2 3 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2
## [1463] 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 4 3 4 3 2 3 4 3 2 3 2 1 2 3 4
## [1497] 5 6 7 8 9 8 7 8 7 6 7 8 7 6 7 6 5 6 7 8 7 6 7 6 5 6 7 6 5 6 5 4 5 6
## [1531] 7 8 7 6 7 6 5 6 7 6 5 6 5 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 7 8
## [1565] 7 6 7 6 5 6 7 6 5 6 5 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 7 6 5 6
## [1599] 5 4 5 6 5 4 5 4 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 6 7 8 7 6 7 6
## [1633] 5 6 7 6 5 6 5 4 5 6 7 6 5 6 5 4 5 6 5 4 5 4 3 4 5 6 7 6 5 6 5 4 5 6
## [1667] 5 4 5 4 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 6 7 6 5 6 5 4 5 6 5 4
## [1701] 5 4 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2 3 4 5 6 5 4 5 4 3 4 5 4 3 4 3 2
## [1735] 3 4 5 4 3 4 3 2 3 4 3 2 3 2
largest_cliques(gump_net)
## [[1]]
## + 9/94 vertices, named, from babf477:
## [1] FORREST   STRONGARM LT DAN    BUBBA     SONG      DALLAS    MAN      
## [8] SGT SIMS  SOLDIER  
## 
## [[2]]
## + 9/94 vertices, named, from babf477:
## [1] FORREST JENNY   EMCEE   MAN #   MAN #1  MAN #2  MAN #3  MAN #5  MEN
vcol <- rep("grey80", vcount(gump_net))
vcol[unlist(largest_cliques(gump_net))] <- "gold"
plot(gump_net, vertex.label=V(gump_net)$name, vertex.color=vcol, vertex.label.cex = 0.5, layout = layout_nicely)

Community Detection

Mittlerweile lassen sich aus der Analyse solcher Cliquen auch größere Communities automatisiert identifizieren. Das Feld der sozialen Netzwerkanalyse hat bereits zahlreiche Algorithmen hervorgebracht, welche unterschiedliche Kriterien für die Einordnung eines Knotens in eine Community anlegen.

Grundsätzlich basieren alle Arten und Ansätze aber auf der Idee, dass bestimmte Knoten sich einander sehr ähnlich sind. Viele Algorithmen ähneln daher den Spielarten der Clusteranalyse oder basieren auf dieser. Aktuell sind im igraph-Paket folgende community-detection-algorithmen enthalten:

  • Edge-betweenness – cluster edge betweenness()
  • Leading eigenvector – cluster leading eigen()
  • Fast-greedy cluster – fast greedy()
  • Louvain cluster – louvain()
  • Walktrap cluster – walktrap()
  • Label propagation – cluster label prop()
  • InfoMAP cluster – infomap()
  • Spinglass cluster – spinglass()
  • Optimal cluster – optimal()

Da die Algorithmen allerdings z.T. unterschiedliche Kriterien heranziehen, unterscheiden sich auch die Ergebnisse voneinander.

ceb <- cluster_edge_betweenness(gump_net1) 
dendPlot(ceb, mode="hclust")

plot(ceb,gump_net1) 

cfg <- cluster_fast_greedy(gump_net1)
dendPlot(cfg, mode="hclust")

plot(cfg,gump_net1)

Analyse des gesamten Netzwerks

edge density

Ein gängiges Merkmal von Netzwerken ist z.B. die Netzwerkdichte. Die Dichte ergibt sich aus der Aufsummierung aller vorhandenen Beziehungen bezogen auf die Zahl der maximal möglichen Verbindungen innerhalb eines Netzwerks. Es ergibt sich ein Wert zwischen 0 und 1, wobei ein Wert nahe Null auf eine niedrige Netzwerkdichte schließen lässt. Mit der Netzwerkdichte sind einige Implikationen für die Funktionsweise des Netzwerkes verbunden. Beispielsweise kann eine hohe Netzwerkdichte die Verbreitung von Innovationen, Neuigkeiten oder den Transfer von Ressourcen begünstigen. Akteure in dichten Netzwerken werden i.d.R. früher von Innovationen erfahren und ausprobieren als Akteure in Netzwerken, die relativ unverbunden sind.

edge_density(gump_net)
## [1] 0.06199954

diameter

Der diameter ist die Länge der längsten Entfernung zwischen zwei Knoten. Hier ist die Unterscheidung zwischen gerichteten und ungerichteten Netzwerken wichtig, weil es hier darauf ankommt, über welche Verbindung man in welche Richtung gehen kann.

diameter(gump_net, directed = FALSE)
## [1] 4
farthest_vertices(gump_net)
## $vertices
## + 2/94 vertices, named, from babf477:
## [1] MARGO            GOVERNOR WALLACE
## 
## $distance
## [1] 4

average path length

Die durchschnittliche Pfadlänge ist ein Konzept, das als durchschnittliche Anzahl von Schritten entlang der kürzesten Pfade für alle möglichen Paare von Netzwerkknoten definiert ist. Ähnlich wie die Dichte, kann es dafür genutzt werden, den Zusammenhalt in einem Netzwerk zu analysieren.

mean_distance(gump_net, directed = FALSE)
## [1] 1.994967

network randomizations

Jedes Netzwerk weist eine strukturelle Signatur auf, die bestimmte selbstorganisierende Prinzipien enthält und sich jeweils individuell durch die oben aufgeführten Kennzahlen auszeichnet. Für ein gegebenes Netzwerk ergibt sich die Stabilität dieser Prinzipien aus der Konstanz allgemeiner sozialer Verhaltensweisen, die wir als Menschen in sozialen Kontexten entwickelt haben. Für ein gegebenes Netzwerk ändern sich diese Kennzahlen also potentiell nur langsam oder wenig.

Diese Organisationsprinzipien können allerdings je nach Kontext mehr oder weniger stark variieren – sie sind deshalb weder deterministisch noch haben sie einen optimalen Wert. Auch die oben aufgeführten Werte, lassen sich ohne weiteren Kontext nur schwer einordnen. Ist eine durchschnittliche Pfaddistanz von round(mean_distance(gump_net, directed = FALSE), 2) viel oder wenig? Hängen die Akteure im Netzwerk besonders dicht zusammen oder nicht?

Wir suchen letztlich also nach Mustern im Netzwerk. Es reicht jedoch nicht aus, die Daten für jeweils ein Muster zu untersuchen, da Strukturen aufeinander aufbauen. Zum Beispiel enthält eine Triade drei Netzwerkverknüpfungen. Wenn ein Netzwerk viele Verbindungen hat, könnte es sein, dass wir besonders viele Cliquen (Triaden) beobachten - allerdings völlig by chance. Die Frage ist dann: Angesichts der Dichte des Netzwerks, sehen wir mehr Cliquen als erwartet?

Exponential random graph models (ERGM) sind eine Familie statistischer Modelle für soziale Netzwerke, die unter gegebenen Netzwerkstrukturen, Rückschlüsse auf Muster in den Daten zulassen. Kurz gesagt, werden bspw. 1000 Netzwerke mit einer gegebenen Knotenanzahl und gegebener Dichte simuliert. Der Algorithmus verteilt die Verbindungen zwischen den Knoten zufällig und anschließend wird für jedes dieser Netzwerke bpsw. die durchschnittliche Distanz errechnet. Im Vergleich zu diesen 1000 Netzwerken lässt sich das Ursprungsnetzwerk dann vergleichen.

# Generate 1000 random graphs
g_random <- vector('list',1000)

for(i in 1:1000){
  
  g_random[[i]] <- sample_gnp(n = gorder(gump_net), 
                              p = edge_density(gump_net), 
                              directed = FALSE)
}

# apply mean_distance on every graph
g_random_meandis <- unlist(lapply(g_random, mean_distance, directed = FALSE))

mean_distance(gump_net, directed = FALSE)
## [1] 1.994967
# graphical comparison to original network
ggplot() + 
  aes(g_random_meandis)+ 
  geom_histogram(bins = 50, colour="black", fill="white")+
  geom_vline(xintercept = mean_distance(gump_net, directed = FALSE), colour="red", linetype = "longdash")

Das ForrestGump-Netzwerk weißt demnach eine sehr geringe durchschnittliche Distanz zwischen den Knoten auf, verglichen mit anderen Netzwerken mit gleicher Dichte und gleicher Anzahl an Knoten. Das ergibt insofern inhaltlich Sinn, dass mit Forrest ein Akteur sehr zentral im Netzwerk ist, der mit nahezu allen anderen Akteuren in einer direkten Verbindung steht.